package 中等.数学;

import java.util.Arrays;

/**
 * 初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。
 * <p>
 * 第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换
 * 一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
 * <p>
 * 找出并返回 n 轮后有多少个亮着的灯泡。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/bulb-switcher
 */
public class 灯泡开关_319 {

    public static void main(String[] args) {

        System.out.println(bulbSwitch(3));

    }

    /**
     * 模拟，false代表关闭，true代表打开
     *
     * @param n
     * @return
     */
    public static int bulbSwitch(int n) {
        int bulbNum = 0;
        boolean[] bulbs = new boolean[n];
        Arrays.fill(bulbs, true);
        for (int i = 1; i <= n; i++) {
            for (int cur = i; cur < bulbs.length; cur += i + 1) {
                bulbs[cur] = !bulbs[cur];
            }
        }
        for (boolean bulb : bulbs) {
            if (bulb) {
                bulbNum++;
            }
        }
        return bulbNum;
    }

    /**
     * TODO  ???
     *
     * @param n
     * @return
     */
    public static int efficientBulbSwitch(int n) {
        return (int) Math.sqrt(n + 0.5);
    }

}
